package com.zm.demo.core.leetcode;


import java.util.HashMap;
import java.util.TreeMap;

public class FirstMissingPositive {

    public int firstMissingPositive(int[] nums) {
        int length = nums.length;
        for(int i = 0 ; i < length; i++){
            if (nums[i] == i+1){
                continue;
            }
            if (nums[i] <= length && nums[i] > 0){
                int tmp = nums[nums[i]-1];
                nums[nums[i]-1] = nums[i];
                nums[i] = tmp;
            }
        }
        for(int i = 0 ; i < length; i++){
            if (nums[i] != i+1){
                return i+1;
            }
        }
        return length+1;
    }

    public int firstMissingPositive1(int[] nums) {
        int length = nums.length;
        TreeMap<Integer,Integer> hashMap = new TreeMap();
        for(int i = 1 ; i <= length; i++){
            hashMap.put(i,i);
        }
        for(int i = 0 ; i < length; i++){
            if (hashMap.get(nums[i]) != null){
                hashMap.remove(nums[i]);
            }
        }
        return hashMap.size() == 0 ? length+1 : hashMap.firstEntry().getValue();
    }

    public static void main(String[]args){

    }
}
